﻿
namespace Leetcode.N1044;

public class Solution
{
    public string LongestDupSubstring(string s)
    {
        var nums = new int[s.Length];
        for (int i = 0; i < nums.Length; i++)
        {
            nums[i] = s[i] - 'a';
        }
        var left = 0;
        var right = s.Length - 1;
        // 太大了会取模运算会可能溢出，没查出问题来
        var mod = 9000000;
        var start = 0;
        var length = -1;

        while (left <= right)
        {
            var count = left + (right - left + 1) / 2;
            var chk = this.Check(nums, count, mod);
            if (chk == -1)
            {
                right = count - 1;
            }
            else
            {
                start = chk;
                length = count;
                left = count + 1;
            }
        }

        return length == -1 ? "" : s.Substring(start, length);
    }

    private int Check(int[] nums, int count, int mod)
    {
        long hash = 0;
        int powMode = this.PowMode(count, mod);

        for (int i = 0; i < count; i++)
        {
            hash = (hash * 26 % mod + nums[i]) % mod;
        }
        var hasSet = new HashSet<(int[] nums, int index, int count, int hashCode)>(new EqualityComparer());
        hasSet.Add((nums, 0, count, (int)hash));
        for (int i = 1; i <= nums.Length - count; i++)
        {
            hash = (hash * 26 % mod - nums[i - 1] * powMode % mod + nums[i + count - 1]) % mod;

            if (hash < 0)
            {
                hash += mod;
            }

            if (!hasSet.Add((nums, i, count, (int)hash)))
            {
                return i;
            }
        }
        return -1;
    }
 
    private int PowMode(int count, int mod)
    {
        long ans = 1;
        for (int i = 0; i < count; i++)
        {
            ans = ans * 26 % mod;
        }
        return (int)ans;
    }

}

public class EqualityComparer : IEqualityComparer<(int[] nums, int index, int count, int hashCode)>
{
    public bool Equals((int[] nums, int index, int count, int hashCode) x, (int[] nums, int index, int count, int hashCode) y)
    {

        for (var i = 0; i < x.count; i++)
        {
            if (x.nums[x.index + i] != y.nums[y.index + i])
            {
                return false;
            }
        }
        return true;
    }

    public int GetHashCode((int[] nums, int index, int count, int hashCode) obj)
    {
        return obj.hashCode;
    }
}